package simple;

/**
 * @author 杜伟毅
 * @version 1.0
 * @since 2025/10/13
 * <p>
 * 35. 搜索插入位置
 * <p>
 * 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
 * <p>
 * 请必须使用时间复杂度为 O(log n) 的算法。
 * <p>
 * 示例 1:
 * <p>
 * 输入: nums = [1,3,5,6], target = 5
 * 输出: 2
 * 示例 2:
 * <p>
 * 输入: nums = [1,3,5,6], target = 2
 * 输出: 1
 * 示例 3:
 * <p>
 * 输入: nums = [1,3,5,6], target = 7
 * 输出: 4
 * <p>
 * <p>
 * 提示:
 * <p>
 * 1 <= nums.length <= 104
 * -104 <= nums[i] <= 104
 * nums 为 无重复元素 的 升序 排列数组
 * -104 <= target <= 104
 * <p>
 * O(log n) 的意思：
 * n代表问题的规模有多大（比如猜数字游戏里的数字范围有多大，或者一个数组里有多少元素）。
 * log n(通常指以2为底的对数) 代表你需要的最多步骤（猜的次数、操作的次数）是多少。
 * 神奇之处在于： 当 n变得超级巨大的时候，log n这个值增长得非常非常慢！
 * 核心思想： 这种高效的算法（比如二分搜索），每次都把问题规模砍掉一半（或者砍掉一大块）。砍一次，问题就小很多。砍几次（log n 次），问题就小到能直接解决了。
 * 总结成一句话：
 * O(log n) 的算法就像一个有魔法的砍刀，不管问题有多大（n 有多大），它都能用非常少的步骤（大约 log n 步）把问题砍到很小然后解决掉。问题规模翻很多很多倍，它需要的步骤才多一点点。这就是它特别高效的原因！
 * 所以，当要求你写一个 O(log n) 的算法时，就是让你用这种“每次砍掉一半”的聪明办法来解决问题，而不是傻傻地一个一个试（O(n)）。最常见的例子就是二分查找。
 */
public class SearchInsertPosition {
    public int searchInsert(int[] nums, int target) {
        // 数组长度（比如有6个数字）
        int n = nums.length;

        // 准备三个工具：
        int left = 0;           // 左指针：指向查找范围的起点（第一个数字）
        int right = n - 1;      // 右指针：指向查找范围的终点（最后一个数字）
        int ans = n;            // 默认答案：如果target最大，就插在最后（第6个位置）

        // 开始"猜数字"游戏（二分查找）
        while (left <= right) {
            // 取中间位置（相当于猜中间的数字）
            // 注意：>>1 相当于除以2（但更快）
            int mid = ((right - left) >> 1) + left;

            // 检查中间的数字
            if (target <= nums[mid]) {
                // 情况1：目标值 <= 中间值
                ans = mid;          // 记录可能的位置（可能是这里，或更左边）
                right = mid - 1;    // 缩小范围到左半部分（往小的方向猜）
            } else {
                // 情况2：目标值 > 中间值
                left = mid + 1;     // 缩小范围到右半部分（往大的方向猜）
            }
        }

        // 返回最终找到的插入位置
        return ans;
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, 5, 6};
//        int target = 5;
//        int target = 2;
//        int target = 7;
        int target = 0;
        SearchInsertPosition position = new SearchInsertPosition();
        System.out.println(position.searchInsert(nums, target));
    }
}
